package com.huawei.M01.iterator.F04;

import java.util.Arrays;
import java.util.PriorityQueue;

public class reCombine {
    public int[] prevPermOpt1(int[] arr) {
        // 从后往前遍历，找到arr[i] < arr[i - 1], 然后找到小于arr[i - 1]的最大值进行交换
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        for (int i = arr.length - 1; i >= 0; i--) {
            queue.add(arr[i]);
            if (i > 0 && arr[i] < arr[i - 1]) {
                while (!queue.isEmpty() && queue.peek() >= arr[i - 1]) {
                    queue.poll();
                }
                int tmp = queue.peek();
                int index = getIndex(tmp, arr, i);
                arr[index] = arr[i - 1];
                arr[i - 1] = tmp;
                break;
            }
        }
        return arr;
    }

    private int getIndex(int tmp, int[] arr, int index) {
        for (int i = index; i < arr.length; i++) {
            if (arr[i] == tmp) {
                return i;
            }
        }
        return arr.length - 1;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new reCombine().prevPermOpt1(new int[]{3, 1, 1, 3})));
        ;
    }
}
